SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>L-notation</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">L-notation</span></span>

</h1>

</header>

<p><i><b>L</b></i>-<b>notation</b> is an <a href="Asymptotic_analysis" title="Asymptotic analysis">asymptotic</a> notation analogous to <a href="Big-O_notation" class="mw-redirect" title="Big-O notation">big-O notation</a>, denoted as <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L_{n}[\alpha ,c]}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{n}[\alpha ,c]}</annotation>

</semantics>

</math></span><img src="./4bc08a186e75571e0bee47eaafc610206275f961.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.623ex; height:2.843ex;" alt="{\displaystyle L_{n}[\alpha ,c]}" loading="lazy"></span> for a <a href="Bound_variable" class="mw-redirect" title="Bound variable">bound variable</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> <a href="Limit_(mathematics)" title="Limit (mathematics)">tending to infinity</a>. Like big-O notation, it is usually used to roughly convey the rate of growth of a <a href="Function_(mathematics)" title="Function (mathematics)">function</a>, such as the <a href="Computational_complexity_theory" title="Computational complexity theory">computational complexity</a> of a particular <a href="Algorithm" title="Algorithm">algorithm</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

<p>It is defined as

</p>

<msub>

</mrow>

</msub>

<msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}</annotation>

</semantics>

</math></span><img src="./40715162d91a34daf9bcfed5f41d8e336417f803.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.754ex; height:3.676ex;" alt="{\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}" loading="lazy"></span></dd></dl>

<p>where <i>c</i> is a positive constant, and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math></span><img src="./b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy"></span> is a constant <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq \alpha \leq 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq \alpha \leq 1}</annotation>

</semantics>

</math></span><img src="./9184b6c2088ccc2e9ac06bfb0964e264c9f6ba53.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.009ex; height:2.343ex;" alt="{\displaystyle 0\leq \alpha \leq 1}" loading="lazy"></span>.

</p><p>L-notation is used mostly in <a href="Computational_number_theory" title="Computational number theory">computational number theory</a>, to express the complexity of algorithms for difficult <a href="Number_theory" title="Number theory">number theory</a> problems, e.g. <a href="Sieve_theory" title="Sieve theory">sieves</a> for <a href="Integer_factorization" title="Integer factorization">integer factorization</a> and methods for solving <a href="Discrete_logarithm" title="Discrete logarithm">discrete logarithms</a>. The benefit of this notation is that it simplifies the analysis of these algorithms. The <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e^{c(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}">

<msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e^{c(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}</annotation>

</semantics>

</math></span><img src="./b2d54f070e791f019f75c13031886deff20769eb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:15.576ex; height:3.176ex;" alt="{\displaystyle e^{c(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}" loading="lazy"></span> expresses the dominant term, and the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e^{o(1)(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}">

<msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e^{o(1)(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}</annotation>

</semantics>

</math></span><img src="./84206132ead507847dbf2e0d7f1301ebbcacc138.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:17.763ex; height:3.176ex;" alt="{\displaystyle e^{o(1)(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}" loading="lazy"></span> takes care of everything smaller.

</p><p>When <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math></span><img src="./b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy"></span> is 0, then

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{n}[\alpha ,c]=L_{n}[0,c]=e^{(c+o(1))\ln \ln n}=(\ln n)^{c+o(1)}\,}</annotation>

</semantics>

</math></span><img src="./5f7d292b6129a9cbfb2d0cacc9bfd1b0a05959ad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:47.631ex; height:3.343ex;" alt="{\displaystyle L_{n}[\alpha ,c]=L_{n}[0,c]=e^{(c+o(1))\ln \ln n}=(\ln n)^{c+o(1)}\,}" loading="lazy"></span></dd></dl>

<p>is a <a href="Polylogarithmic_function" title="Polylogarithmic function">polylogarithmic function</a> (a <a href="Polynomial_function" class="mw-redirect" title="Polynomial function">polynomial function</a> of ln <i>n</i>);

</p><p>When <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math></span><img src="./b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy"></span> is 1 then

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{n}[\alpha ,c]=L_{n}[1,c]=e^{(c+o(1))\ln n}=n^{c+o(1)}\,}</annotation>

</semantics>

</math></span><img src="./adf4c238d6a2edb4f96246252ca13523fc8353fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:41.736ex; height:3.343ex;" alt="{\displaystyle L_{n}[\alpha ,c]=L_{n}[1,c]=e^{(c+o(1))\ln n}=n^{c+o(1)}\,}" loading="lazy"></span></dd></dl>

<p>is a fully <a href="Exponential_function" title="Exponential function">exponential function</a> of ln <i>n</i> (and thereby polynomial in <i>n</i>).

</p><p>If <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math></span><img src="./b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy"></span> is between 0 and 1, the function is <a href="Sub-exponential_time" class="mw-redirect" title="Sub-exponential time">subexponential</a> of ln <i>n</i> (and <a href="Superpolynomial" class="mw-redirect" title="Superpolynomial">superpolynomial</a>).

</p>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<p>Many general-purpose <a href="Integer_factorization" title="Integer factorization">integer factorization</a> algorithms have <a href="Time_complexity#Sub-exponential_time" title="Time complexity">subexponential time complexities</a>. The best is the <a href="General_number_field_sieve" title="General number field sieve">general number field sieve</a>, which has an expected running time of

</p>

<msub>

</mrow>

</msub>

</mrow>

<msup>

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{n}[1/3,c]=e^{(c+o(1))(\ln n)^{1/3}(\ln \ln n)^{2/3}}}</annotation>

</semantics>

</math></span><img src="./fba4f613c49802383fab0422f391cc98bec823c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:34.345ex; height:3.843ex;" alt="{\displaystyle L_{n}[1/3,c]=e^{(c+o(1))(\ln n)^{1/3}(\ln \ln n)^{2/3}}}" loading="lazy"></span></dd></dl>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c=(64/9)^{1/3}\approx 1.923}</annotation>

</semantics>

</math></span><img src="./c81d7f835308f76e0d29557e8c0cecc15279119b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.658ex; height:3.343ex;" alt="{\displaystyle c=(64/9)^{1/3}\approx 1.923}" loading="lazy"></span>. The best such algorithm prior to the number field sieve was the <a href="Quadratic_sieve" title="Quadratic sieve">quadratic sieve</a> which has running time

</p>

<msub>

</mrow>

</msub>

</mrow>

<msup>

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{n}[1/2,1]=e^{(1+o(1))(\ln n)^{1/2}(\ln \ln n)^{1/2}}.\,}</annotation>

</semantics>

</math></span><img src="./db0fcb8338a8140b3ef7c098bed64903e9c3f214.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:35.644ex; height:3.843ex;" alt="{\displaystyle L_{n}[1/2,1]=e^{(1+o(1))(\ln n)^{1/2}(\ln \ln n)^{1/2}}.\,}" loading="lazy"></span></dd></dl>

<p>the third-fastest known factoring method: <a href="Lenstra_elliptic-curve_factorization" title="Lenstra elliptic-curve factorization">Lenstra elliptic-curve factorization</a> , which has running time

</p>

<msub>

</mrow>

</msub>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

<msup>

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{n}[1/2,2^{1/2}]=e^{(2^{1/2}+o(1))(\ln n)^{1/2}(\ln \ln n)^{1/2}}.\,}</annotation>

</semantics>

</math></span><img src="./7a1dffb13c62dd9f283c3e9cd15dec0115960958.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:40.509ex; height:3.843ex;" alt="{\displaystyle L_{n}[1/2,2^{1/2}]=e^{(2^{1/2}+o(1))(\ln n)^{1/2}(\ln \ln n)^{1/2}}.\,}" loading="lazy"></span></dd></dl>

<p>For the <a href="Elliptic_curve" title="Elliptic curve">elliptic curve</a> <a href="Discrete_logarithm" title="Discrete logarithm">discrete logarithm</a> problem, the fastest general purpose algorithm is the <a href="Baby-step_giant-step" title="Baby-step giant-step">baby-step giant-step</a> algorithm, which has a running time on the order of the square-root of the group order <i>n</i>. In <i>L</i>-notation this would be

</p>

<msub>

</mrow>

</msub>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{n}[1,1/2]=n^{1/2+o(1)}.\,}</annotation>

</semantics>

</math></span><img src="./b529316c3a0906d16002862b62245c0c5f20bce4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.181ex; height:3.343ex;" alt="{\displaystyle L_{n}[1,1/2]=n^{1/2+o(1)}.\,}" loading="lazy"></span></dd></dl>

<p>The existence of the <a href="AKS_primality_test" title="AKS primality test">AKS primality test</a>, which runs in <a href="Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a>, means that the time complexity for <a href="Primality_testing" class="mw-redirect" title="Primality testing">primality testing</a> is known to be at most

</p>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{n}[0,c]=(\ln n)^{c+o(1)}\,}</annotation>

</semantics>

</math></span><img src="./424894391b43378ab257339922459690a6ec38f0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.436ex; height:3.343ex;" alt="{\displaystyle L_{n}[0,c]=(\ln n)^{c+o(1)}\,}" loading="lazy"></span></dd></dl>

<p>where <i>c</i> has been proven to be at most 6.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

<p>L-notation has been defined in various forms throughout the literature. The first use of it came from <a href="Carl_Pomerance" title="Carl Pomerance">Carl Pomerance</a> in his paper "Analysis and comparison of some integer factoring algorithms".<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> This form had only the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math></span><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"></span> parameter: the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math></span><img src="./b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy"></span> in the formula was <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1/2}</annotation>

</semantics>

</math></span><img src="./e308a3a46b7fdce07cc09dcab9e8d8f73e37d935.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.487ex; height:2.843ex;" alt="{\displaystyle 1/2}" loading="lazy"></span> for the algorithms he was analyzing. Pomerance had been using the letter <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math></span><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"></span> (or lower case <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l}</annotation>

</semantics>

</math></span><img src="./829091f745070b9eb97a80244129025440a1cfac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}" loading="lazy"></span>) in this and previous papers for formulae that involved many logarithms.

</p><p>The formula above involving two parameters was introduced by <a href="Arjen_Lenstra" title="Arjen Lenstra">Arjen Lenstra</a> and <a href="Hendrik_Lenstra" title="Hendrik Lenstra">Hendrik Lenstra</a> in their article on "Algorithms in Number Theory".<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> It was introduced in their analysis of a <a href="Discrete_logarithm" title="Discrete logarithm">discrete logarithm</a> algorithm of <a href="Don_Coppersmith" title="Don Coppersmith">Coppersmith</a>. This is the most commonly used form in the literature today.

</p><p>The Handbook of Applied Cryptography defines the L-notation with a big <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O}</annotation>

</semantics>

</math></span><img src="./9d70e1d0d87e2ef1092ea1ffe2923d9933ff18fc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.773ex; height:2.176ex;" alt="{\displaystyle O}" loading="lazy"></span> around the formula presented in this article.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> This is not the standard definition. The big <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O}</annotation>

</semantics>

</math></span><img src="./9d70e1d0d87e2ef1092ea1ffe2923d9933ff18fc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.773ex; height:2.176ex;" alt="{\displaystyle O}" loading="lazy"></span> would suggest that the running time is an upper bound. However, for the integer factoring and discrete logarithm algorithms that L-notation is commonly used for, the running time is not an upper bound, so this definition is not preferred.

</p>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text">Hendrik W. Lenstra Jr. and Carl Pomerance, "Primality testing with Gaussian periods", preprint, 2011, <a rel="nofollow" class="external free" href="http://www.math.dartmouth.edu/~carlp/aks041411.pdf">http://www.math.dartmouth.edu/~carlp/aks041411.pdf</a>.</span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text">Carl Pomerance, "Analysis and comparison of some integer factoring algorithms", In Mathematisch Centrum Computational Methods in Number Theory, Part 1, pp. 89-139, 1982, <a rel="nofollow" class="external free" href="http://www.math.dartmouth.edu/~carlp/PDF/analysiscomparison.pdf">http://www.math.dartmouth.edu/~carlp/PDF/analysiscomparison.pdf</a></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text">Arjen K. Lenstra and Hendrik W. Lenstra, Jr, "Algorithms in Number Theory", in Handbook of Theoretical Computer Science (vol. A): Algorithms and Complexity, 1991.</span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text">Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996. <style data-mw-deduplicate="TemplateStyles:r1238218222">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-8493-8523-7</bdi>. <a rel="nofollow" class="external free" href="http://www.cacr.math.uwaterloo.ca/hac/">http://www.cacr.math.uwaterloo.ca/hac/</a>.</span>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-08-03" href="https://en.wikipedia.org/wiki/?title=L-notation&oldid=1304008780">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>